# -*- coding: utf-8 -*-
"""
merge-sort
Soraia Janeiro, 6051
12-03-2014
"""
import math
import random

def merge(A, p, q, r):
	n1 = q - p + 1
	n2 = r - q
	L = list()
	R = list()
	for i in range (0, n1):
		L.append(A[p + i])
		pass
	for j in range (0, n2):
		R.append(A[q + j + 1])
		pass
	L.append(999999999999999)
	R.append(999999999999999)
	#print "Lista L = " , L
	#print "Lista R = " , R
	i = 0
	j = 0
	

	for k in range (p, (r+1)):
		if (L[i] <= R[j]):
			A[k] = L[i]
			i = i + 1
			pass
		else:
			A[k] = R[j]
			j = j + 1
			pass
		pass
	
	return A

def mergeSort(A,p,r):
	if (p < r):
		q = int(math.floor((p + r) / 2.0))
		A = mergeSort(A, p, q)
		A = mergeSort(A, q + 1, r)
		A = merge(A, p, q, r)
		pass
	return A


lista = []
for i in xrange(0, 100):
	num = random.randint(0,100)
	lista.append(num)
	pass

A = lista
p = 0
q = 10
r = 99
print "Lista gerada: ", A
print "Lista Ordenada: ", mergeSort(A, p, r)			
			
